package com.timous.others;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 */
public class _3_无重复字符的最长子串 {

    public static void main(String[] args) {
        String s =  "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s));
    }


    public static int lengthOfLongestSubstring(String s) {
        if (s == null) return 0;
        char[] chars = s.toCharArray();
        if (chars.length == 0) return 0;
        int[] array = new int[128];
        for (int i = 0; i < array.length; i++) {
            array[i] = -1;
        }
        array[chars[0]] = 0;
        //扫描我们的字符串
        int li = 0;
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            // chars[i] 上次出现的位置
            int pi = array[chars[i]];
            if (li <= pi){
                li = pi + 1;
            }
            max = Math.max(max , i - li + 1);
            //每次都要添加字符最新位置
            array[chars[i]] = i;
        }

        return max;
    }
    public static int lengthOfLongestSubstring3(String s) {
        if (s == null) return 0;
        char[] chars = s.toCharArray();
        if (chars.length == 0) return 0;
        int[] array = new int[26];
        for (int i = 0; i < array.length; i++) {
            array[i] = -1;
        }
        array[0] = 0;
        //扫描我们的字符串
        int li = 0;
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            // chars[i] 上次出现的位置
            int pi = array[chars[i] - 97];
            if (li <= pi){
                li = pi + 1;
            }
            max = Math.max(max , i - li + 1);
            //每次都要添加字符最新位置
            array[chars[i] - 97] = i;
        }

        return max;
    }
    public static int lengthOfLongestSubstring2(String s) {
        if (s == null) return 0;
        char[] chars = s.toCharArray();
        if (chars.length == 0) return 0;
        Map<Character , Integer> pre = new HashMap<>();
        pre.put(chars[0] , 0);
        //扫描我们的字符串
        int li = 0;
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            // chars[i] 上次出现的位置
            int pi = pre.getOrDefault(chars[i], -1);
            if (li <= pi){
                li = pi + 1;
            }
            max = Math.max(max , i - li + 1);
            pre.put(chars[i] , i);
        }

        return max;
    }
}
